1. Field of the Present Invention
The present invention relates generally to the computing and microelectronics fields. More specifically, the present invention relates to a Boolean-based processor architecture that is capable of the short-circuit evaluation of Conjunctive Normal Form (“CNF”) Boolean expressions, Disjunctive Normal Form (“DNF”) Boolean expressions, or both. The Boolean processor of the present invention provides an inexpensive, scalable, and efficient means for computing in environments typically suited for application-specific microprocessors and microcontrollers, such as monitoring and automation environments.
2. Background
A microprocessor is a general-purpose computing architecture, also known as a central processing unit (CPU). The microprocessor includes an arithmetic logic unit (ALU), an accumulator, a plurality of registers, a program counter, a stack pointer, a clock circuit, and a plurality of interrupt circuits. In building a complete computing system, the microprocessor must be supplemented with external components, such as a random-access memory (RAM) and a read-only memory (ROM), an oscillator, a plurality of memory decoders, a plurality of Input/Output (I/O) interfaces (ports), and a plurality of other devices, such as video displays and disk drives. The microprocessor is designed to perform a wide variety of calculations with data and return the results to a user or another machine. The microprocessor achieves this computing power through the use of a sophisticated instruction set that may contain a plurality of instructions for performing arithmetic operations, bit movement operations, memory fetch and store operations, etc. Because of the complexity of the calculations that the microprocessor performs, the programs that control its operation are generally relatively large, requiring the use of mass storage devices to house them. When needed for a specific calculation or task, a program is loaded into the system RAM and executed by the microprocessor.
The primary design factors related to the microprocessor are flexibility and expandability, allowing the microprocessor to handle almost any task. This adaptability has resulted in a relatively large demand for the microprocessor and has enabled manufacturers to mass-produce them, resulting in a relatively inexpensive and disposable product.
Like the microprocessor, a microcontroller is also a general-purpose computing architecture. The microcontroller differs from the microprocessor, however, in that it can operate as a complete, stand-alone computer system. The microcontroller includes all of the components of the microprocessor, in addition to its own RAM, ROM, plurality of counters, and I/O ports. The microcontroller is also relatively flexible and can be used in a plurality of applications, however, the microcontroller is intended for use in a relatively static environment, requiring its programs to change minimally over time. The microcontroller is primarily intended to be used to control the environment within which it operates. The microcontroller is typically used in embedded system applications for monitoring and automation purposes. The microcontroller can be found in, for example, appliances (such as microwave ovens, refrigerators, televisions, VCRs, and stereos), automobiles (such as in engine control systems, diagnostics systems, and climate control systems), environmental control systems (such as in factories, greenhouses, and homes), instrumentation arrays, and aerospace systems.
The microprocessor differs from the microcontroller in their sets of operational codes. The microprocessor has far more operational codes for moving data to and from an external memory than the microcontroller, which may only have a few such operational codes. From an internal bit-handling perspective, the microcontroller has far more internal bit-handling operational codes than the microprocessor, which may only have a few. The architecture of both the microprocessor and the microcontroller are intended for mass use and are designed for flexibility and expandability. Each has the goal of supporting a wide range of applications. While the primary use of the microprocessor is for calculation-intensive computing, the microcontroller is designed to handle smaller calculations and to control its environment.
The short-circuit evaluation of a Boolean expression or operation is simply the abandonment of the remainder of the expression or operation once its value has been determined. If the outcome of the expression or operation can be determined prior to its full evaluation, it makes sense to save processing cycles by avoiding the remaining, unnecessary, conditional tests of the expression or operation. In other words, the short-circuit evaluation of a Boolean expression is a technique that specifies the partial evaluation of expressions involving AND and OR operations.
What is needed is a microprocessor and/or a microcontroller that is capable of evaluating complex Boolean expressions that are in Conjunctive Normal Form (CNF). Disjunctive Normal Form (DNF) Boolean expressions can also be incorporated into the architecture of the microprocessor and/or the microcontroller, however, there are inefficiencies associated with the processing of the DNF equivalents of CNF expressions.
A Boolean expression is in DNF if it is expressed as the sum (OR) of products (AND). That is, the Boolean expression B is in DNF if it is written as:A1 OR A2 OR A3 OR . . . Anwhere each term Ai is expressed as:T1 AND T2 AND . . . AND Tmwhere each term Ti is either a simple variable, or the negation (NOT) of a simple variable. Each term Ai is referred to as a “minterm”. A Boolean expression is in CNF if it is expressed as the product (AND) of sums (OR). That is, the Boolean expression B is in CNF if it is written as:O1 AND O2 AND O3 AND . . . Onwhere each term Oi is expressed as:T1 OR T2 OR . . . OR Tmwhere each term Ti is either a simple variable, or the negation (NOT) of a simple variable. Each term Oi is referred to as a “maxterm”. The terms “minterm” and “maxterm” can also be referred to as “disjunct” and “conjunct”, respectively.
The short-circuit evaluations of a CNF Boolean expression and a DNF Boolean expression are handled differently. In the case of a CNF expression, short-circuiting can occur if any of the conjuncts evaluates to false. In the following example,(AvB)(CvD)if either of the conjuncts, (AvB) or (CvD), evaluates to false, the expression also evaluates to false. If (AvB) evaluates to false, the remainder of the expression can be eliminated, thereby saving the time required to evaluate the other conjunct. In contrast to CNF short-circuit evaluation, a DNF expression can be short-circuited if any of the disjuncts evaluates to true. Using the previous example in DNF,(AC)v(AD)v(BC)v(BD)if any of the disjuncts, (AC), (AD), (BC), or (BD), evaluates to true, the expression also evaluates to true. For example, if (AC) evaluates to true, the evaluation of the remaining three disjuncts can be eliminated, since their values are irrelevant to the outcome of the expression.
Thus, the short-circuit evaluation of both CNF and DNF expressions becomes increasingly valuable, in terms of cycle savings, as the complexity of the expressions increases. In large scale monitoring and automation applications, the short-circuit evaluation of both CNF and DNF expressions is essential.
The Boolean processor is an architecture that is designed to provide optimal performance for computing complex Boolean expressions. The Boolean processor is intended for use in, among other things, monitoring and automation applications. The Boolean processor is built for speed and efficiency via its ability to perform the short-circuit evaluation of Conjunctive Normal Form (CNF) Boolean expressions. It provides enhanced computing performance, in terms of the number of instructions required to perform equivalent operations, to that of other general-purpose architectures. The Boolean processor is described in USPTO patent application Ser. No. 10/075,917. This processor will be referred to as the CNF Boolean processor.
A Disjunctive Normal Form (DNF) Boolean processor is also described in the Provisional Patent Application titled “DNF Boolean Processor” by Kenneth E. Koch III. The DNF Boolean processor is a similar architecture to the Boolean processor with the exception that it is designed to perform short-circuit evaluations on Boolean expressions in Disjunctive Normal Form.